package nodeList;

import java.util.Arrays;
import java.util.List;

/**
 * @author gaolainan
 */
public class ReverseNodeList
{

    public static void main(String[] args)
    {
        // 待排序的数组
        int[] nums = {1, 56, 8, 9, 65, 88,10};
        int[] a = sort(nums);
        for (int i = 0; i < a.length; i++)
        {
            System.out.println(a[i]);
        }
    }

    public ListNode ReverseList(ListNode head) {
        ListNode pre = head;
        ListNode cur = null;
        while(pre != null){
            ListNode next = pre.next;
            pre.next = cur;
            cur = pre;
            pre = next;
        }

        return cur;
    }


    public static int[] sort(int[] source){
        int[] arr = Arrays.copyOf(source,source.length);
        if (arr.length < 2){
            return arr;
        }
        int mid = (int)Math.floor(source.length / 2);
        int[] left = Arrays.copyOfRange(source,0,mid);
        int[] right = Arrays.copyOfRange(source,mid,source.length);

        return merge(sort(left), sort(right));
    }

    public static int[] merge(int[] left, int[] right){
        int[] res = new int[left.length + right.length];
        int i = 0;
        while(left.length != 0 && right.length != 0){
            if (left[0] < right[0]){
                res[i++] = left[0];
                left = Arrays.copyOfRange(left,1,left.length);
            }else{
                res[i++] = right[0];
                right = Arrays.copyOfRange(right,1,right.length);
            }
        }

        while(left.length != 0){
            res[i++] = left[0];
            left = Arrays.copyOfRange(left,1,left.length);
        }

        while(right.length != 0){
            res[i++] = right[0];
            right = Arrays.copyOfRange(right,1,right.length);
        }
        return res;
    }

}
